package com.minglan.leetcode.java.solution2103;

import java.util.ArrayList;
import java.util.List;

/*
 * 2021.3.7
 * 131. 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]
 */
public class Partition {

    public List<List<String>> partition(String s) {
    	List<List<String>> ret=new ArrayList<>();
    	checkString(s, 0, new ArrayList<String>(), ret);
    	return ret;
    }

    public void checkString(String s,int start,List<String> plan,List<List<String>> ret) {
        if(start>=s.length()) {
        	System.out.println("start="+start+" string="+s);
            ret.add(new ArrayList<>(plan));
            return;
        }
        for(int i=start;i<s.length();i++) {
            String substr = s.substring(start,i+1);
            System.out.println(substr);
            if(!isPalindrome(substr)) {
                System.out.println("string=["+s+"] start="+ start+" and false and i="+i+" plan="+plan);
                continue;
            }
            plan.add(substr);
            int index=plan.size();
            System.out.println("string=["+s+"] start="+ start+" and true and i="+i+" plan="+plan);
            checkString(s,i+1,plan,ret);
            System.out.println(plan+" size="+plan.size());
            plan.remove(plan.size()-1);
        }
    }
    
    /*
     * .判断一个字符串是否是回文串
     */
    public boolean isPalindrome(String s) {
    	byte[] buf=s.getBytes();
    	int i=0;
    	int j=buf.length-1;
    	while(i<j) {
    		if ( buf[i]!=buf[j] ) return false;
    		i++;
    		j--;
    	}
    	return true;
    }
    
	public static void main(String[] args) {
		Partition p = new Partition();
		System.out.println(p.partition("aabbaacc"));

	}

}
